1. Field of the Invention
The present invention relates to a content addressable memory or an associative memory comprising a number of word memories each for storing digital data in units of words, and having such a function that retrieval data are input to the word memories and the word memories, which have stored digital data having a bit pattern coincident with that of the retrieval data in its entirety or in a part specified, are retrieved, and further relates a method of the use of the content addressable memory.
2. Description of the Related Art
Recently, there has been proposed a content addressable memory or an associative memory provided with the retrieval function as mentioned above.
FIG. 6 is a circuit block diagram of the conventional content addressable memory by way of example.
Referring to FIG. 6, a content addressable memory 10 is provided with a number of word memories 11a, 11b, . . . , 11n each consisting of a 5-bits serial memory. Further, the content addressable memory 10 comprises a retrieval register 12 which is adapted to latch a word of retrieval data when it is entered the retrieval register 12. A bit pattern of the retrieval data latched in the retrieval register 12 in its entirety or in a part specified is compared with a bit pattern of the portion corresponding to the bit pattern of the latched retrieval data with respect to data stored in each of the word memories 11a, 11b, . . . , 11n. As a result of the comparison, if there are found any of the word memories 11a, 11b, . . . , 11n of which the bit pattern is coincident with that of the retrieval data, a match signal given by a logic "1" (here 5.0 volt) will appear on the associated ones of match lines 14a, 14b, ..., 14n which are provided in conjunction with the word memories 11a, 11b, . . . , 11n, respectively. On the other hand, a mismatch signal given by a logic "0" will appear on the remaining ones of the match lines 14a, 14b, . . . , 14n.
Assuming that the signals "0", "1", "0", "0", "1" . . . , "0" appear on the flag lines 14a, 14b, . . . , 14n, respectively, these signals are applied to a priority encoder 15. The priority encoder 15 is so arranged to output an address signal corresponding to the highest priority match line given with a highest priority among the match lines (here, the match lines 14b and 14e) on which the match signal given by a logic "1" appears. Supposing that the priority is higher as alphabet of a suffix of the reference character becomes younger, in this case, the match line 14b is selected as the highest priority match line. Thus, the priority encoder 15 outputs an address signal AD corresponding to the highest priority match line 14b, which address signal AD is passed to an address decoder 16. The address decoder 16 decodes the received address signal AD and outputs an access signal (here a signal given by a logic "1" to the associated one (here a word line 17b) of word lines 17a, 17b, . . . , 17n which are provided in conjunction with the word memories 11a, 11b, . . . , 11n, respectively. Thus, data stored in the word memory 11b associated with the word line 17b on which the access signal appears is read out to an output register 18 and latched therein.
If the data read out in this way is not a desired one, the match line 14b is masked by means of entry of such information so that the associated signal on the flag line 14b is changed from the logic "1" to the logic "0". Thus, the match line 14e serves now as the highest priority match line, so that data stored in the associated word memory 11e is read out to the output register 18.
As described above, according to the content addressable memory 10, the contents or data stored in a number of word memories 11a, 11b, . . . , 11n are retrieved using the retrieval data in its entirety or a part specified, so that an address of the word memory corresponding to the match data is generated, and thus it is possible to read out the whole data stored in the word memory.
The content addressable memory arranged in such a way as mentioned above, however, may be associated with the following drawbacks in a case where a match signal "1" appears on a number of match signal lines.
FIG. 7 is a view useful for explanation of the drawbacks in such a case.
It is assumed that when a data retrieval is carried out using "ken" as a retrieval data, five match data as shown in FIG. 7 are obtained. Incidentally, it is noted that the five Chinese characters " ", " ", " ", " "," " are pronounced in Japanese as [ken], but they are mutually different in meaning. Supposing that the priority is given in the named order as shown in the figure and a desired data is "ken ", it is informed that first read out data "ken " is not a desired one, next, it is informed that second read out data "ken " is also not a desired one, and the similar operation is repeatedly performed until a desired data "ken " is located. This procedure takes much time for the data retrieval.